#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""
判断edges list组成的undirected graph 是不是一棵树
"""


from collections import defaultdict


class Solution:

    def validTree(self, n, edges):
        # return self.validTree_DFS(n, edges)
        # return self.validTree_union_find1(n, edges)
        return self.valid_tree_union_find2(n, edges)

    # =================== 有向无环图的性质 =====================
    # 1: has n-1 edges
    # 2: acyclic
    # 使用"并查集"或者"深度/广度搜索" 判断是否有环
    def valid_tree_by_property(self, n, edges):
        if len(edges) != n-1:
            return False
        else:
            return True

    # =================== solution union find =====================
    def valid_tree_union_find2(self, n, edges):
        if not self.valid_tree_by_property(n, edges):
            return False

        self.nodes_parent = {i:-1 for i in range(n)}             # 父亲初始化为-1, 负数表示union-set个数, 负数表示parent是自己
                                                                 # union-set的make_set()操作

        for n1, n2 in edges:
            # if not self.union_by_size(n1, n2):
            if not self.union_by_rank(n1, n2):
                return False

        return True

    def find_parent(self, node_label):
        # 注意: 这里递归修改parent
        parent_label = self.nodes_parent[node_label]
        # if parent_label == self.nodes_parent[parent_label]:
        # print('find node %s, parent %s' % (node_label, self.nodes_parent[node_label]))
        if parent_label < 0:
            # print('return node_label %s' % node_label)
            # print('size %s' % self.nodes_parent[node_label])
            # print('===================  =====================\n')
            return node_label

        self.nodes_parent[node_label] = self.find_parent(parent_label)
        return self.nodes_parent[node_label]

    def union_by_rank(self, n1, n2):
        # union by depth
        p1 = self.find_parent(n1)
        p2 = self.find_parent(n2)

        # 两个根节点连起来: 拥有parent
        # self.nodes_parent[n2] = p1        # ERROR: 注意不是连接节点: 而是根节点

        if p1 == p2:
            # print('has undirected cycle')
            # cycle in graph
            return False

        rank_1 = -self.nodes_parent[p1]
        rank_2 = -self.nodes_parent[p2]
        # if rank_1 == rank_2:
        #     self.nodes_parent[p1] = p2
        #     self.nodes_parent[p2] = -(rank_1 + 1)   # 高度相同时高度加1
        # elif rank_1 < rank_2:
        #     self.nodes_parent[p1] = p2
        #     self.nodes_parent[p2] = -(rank_2)
        # else:
        #     self.nodes_parent[p2] = p1
        #     self.nodes_parent[p1] = -(rank_1)
        if rank_1 <= rank_2:
            little_rank = rank_1
            great_rank = rank_2
            child = p1
            parent = p2
        else:
            little_rank = rank_2
            great_rank = rank_1
            child = p2
            parent = p1

        new_rank = max(little_rank + 1, great_rank)
        self.nodes_parent[child] = parent
        self.nodes_parent[parent] = -new_rank

        return True

    def union_by_size(self, n1, n2):
        p1 = self.find_parent(n1)
        p2 = self.find_parent(n2)

        # 两个根节点连起来: 拥有parent
        # self.nodes_parent[n2] = p1        # ERROR: 注意不是连接节点: 而是根节点

        if p1 == p2:
            # print('has undirected cycle')
            return False

        size_1 = -self.nodes_parent[p1]
        size_2 = -self.nodes_parent[p2]
        if size_1 < size_2:
            # print('merge (%s ---> %s)' % (p1, p2))
            # print('size (%s, %s)' % (size_1, size_2))
            # print('new size (%s)' % -(size_1 + size_2))
            # print('===================  ==========================================\n')
            self.nodes_parent[p1] = p2                 # NOTE: 不用在意大小, 根节点相连即可.
            self.nodes_parent[p2] = -(size_1 + size_2) # NOTE: 不用在意大小, 根节点相连即可.
        else:
            # print('merge (%s ---> %s)' % (p2, p1))
            # print('size (%s, %s)' % (size_1, size_2))
            # print('new size (%s)' % -(size_1 + size_2))
            # print('===================  ==========================================\n')
            self.nodes_parent[p2] = p1                 # NOTE: 不用在意大小, 根节点相连即可.
            self.nodes_parent[p1] = -(size_1 + size_2) # NOTE: 不用在意大小, 根节点相连即可.

        return True

    # =================== solution1  =====================
    def validTree_union_find1(self, n, edges):
        # 使用并查集的方式来做
        if n-1 != len(edges):
            return False

        self.nodes_descendants = {i:[i] for i in range(n)}      # 子孙初始化为自己
        self.nodes_parent = {i:i for i in range(n)}             # 父亲初始化为自己

        for n1, n2 in edges:
            valid = self.update_union(n1, n2)
            if not valid:
                return False

        return len(self.nodes_descendants[0]) == n      # 避免孤岛的存在

    def update_union(self, n1, n2):
        # 比较这两个节点的父亲, 然后合并到小父亲节点中
        parent1 = self.nodes_parent[n1]
        parent2 = self.nodes_parent[n2]

        if parent1 == parent2:
            # 两个节点已经具有相同的根, 已经可以构成树, 如果再多余连接, 构成环loop
            # 避免有环的存在
            print('exist loop in undirected graph')
            return False

        little = min(parent1, parent2)
        great  = max(parent1, parent2)
        self.union_change_parent(great, little)
        return True

    def union_change_parent(self, src_parent, dst_parent):
        assert src_parent > dst_parent

        for descendant in self.nodes_descendants[src_parent]:
            self.nodes_parent[descendant] = dst_parent
        self.nodes_descendants[dst_parent] += self.nodes_descendants[src_parent]
        self.nodes_descendants[src_parent].clear()

    # =================== solution2  =====================
    def validTree_DFS(self, n, edges):
        '''
        把大label node放到 小label node的neighbors中, 这种方式是不行的.
        如下图: 如果从小到大访问, 下图只能从0访问到100, 50无法到达.

               50   0
                \ /
                 |
                100

        因为是树, 一定没有孤立节点, 所以0可以作为root. 然后DFS遍历下去.
        '''
        # self.nodes = [UDNode(i) for i in range(n)]

        if n-1 != len(edges):
            return False

        self.nodes = defaultdict(list)
        self.build_neighbors(edges)
        self.visited = set()
        valid = self.check_loop_rec_iterate(0, -1)

        # 有可能还有孤立节点: self.visited !=n 表示有孤立节点
        # print('valid %s' % valid)
        # print(len(self.visited) == n)
        # print(len(self.visited))
        # print(self.visited)
        # for label in self.visited:
        #     print(self.nodes[label])

        return valid and len(self.visited) == n

    def build_neighbors(self, edges):
        for n1, n2 in edges:
            # little = min([n1, n2])
            # great  = max([n1, n2])
            # self.nodes[little].append(great)
            # 这里建立了双向连接
            self.nodes[n1].append(n2)
            self.nodes[n2].append(n1)

    def check_loop_rec_iterate(self, label, parent):
        # 1 ----2----- 3
        # |            |
        # |            |
        # |            |
        # 6-----5------4

        # 如果出现环: "1"深度深度搜索时通过2, 3, 4,5遍历到6. 然后1通过邻居又遍历到6
        # 会出现两次遍历: 如果无向图是一棵树, 那么不会出现环(edges=nodes-1)

        if label in self.visited:
            return False

        self.visited.add(label)

        for nei in self.nodes[label]:
            # NOTE: 母子双向连接重复判断continue即可
            if nei == parent:
                continue

            valid = self.check_loop_rec_iterate(nei, label)
            if not valid:
                return valid        # 直接break 返回

        return True


def main():
    print("start main")

    from q178_input import l, size

    s = Solution()
    ret = s.validTree(5, [[0, 1], [0, 2], [0, 3], [1, 4]])
    ret = s.validTree(5, [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]])
    ret = s.validTree(10, [[0,1],[5,6],[6,7],[9,0],[3,7],[4,8],[1,8],[5,2],[5,3]])
    # ret = s.validTree(size, l)
    # ret = s.validTree(5, [
    #     [1, 3],
    #     [3, 0],
    #     [4, 0],
    #     [2, 3]
    # ])
    print(ret)

if __name__ == "__main__":
    main()
